package Solutions;

import org.w3c.dom.ls.LSInput;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @Classname LetterCombinations
 * @Description TODO
 * @Date 2021/6/18 11:04
 * @Created by ASUS
 * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
 *
 * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 * https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
 */
public class LetterCombinations {

    private static final Map<Character, String> MAP = new HashMap<>();
    static {
        MAP.put('2', "abc");
        MAP.put('3', "def");
        MAP.put('4', "ghi");
        MAP.put('5', "jkl");
        MAP.put('6', "mno");
        MAP.put('7', "pqrs");
        MAP.put('8', "tuv");
        MAP.put('9', "wxyz");
    }

    public List<String> letterCombinations(String digits) {
        List<String> ans = new ArrayList<>();
        if (digits.length() == 0) return ans;

        dfs(digits, new StringBuilder(), ans, 0, 0);

        return ans;
    }

    public void dfs(String digits, StringBuilder sb, List<String> ans, int level, int index) {
        if (level == digits.length()) {
            ans.add(sb.toString());
//            System.out.println(sb.toString());
            return;
        }
        for (char c : MAP.get(digits.charAt(index)).toCharArray()) {
            sb.append(c);
            dfs(digits, sb, ans, level + 1, index + 1);
            sb.deleteCharAt(sb.length() - 1);
        }

    }

    public static void main(String[] args) {
        new LetterCombinations().letterCombinations("23");
    }
}
